import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;

class Solution {

    public static void main(String[] args) {
        Map<Integer,Integer> map = new LinkedHashMap<Integer,Integer>(4,0.75f,true);
        map = new HashMap<>(4);
        System.out.println();
        for (int i = 0; i< 10; ++i){
            map.put(1+i*4,1);
        }
        System.out.println();
    }

    public boolean backspaceCompare(String S, String T) {
        char[] s = new char[S.length()];
        int sc = toChars(S, s);
        char[] t = new char[T.length()];
        int tc = toChars(T, t);
        if (tc != sc) return false;
        while (--sc >= 0 && t[sc] == s[sc]) ;
        //sc == -1 表示比完最后一个元素且两者相等
        return sc == -1;
    }

    private int toChars(String str, char[] cs) {
        int cnt = 0;
        for (int i = 0; i < str.length(); ++i) {
            char c = str.charAt(i);
            if (c == '#') {
                if (cnt > 0) --cnt;
            } else {
                cs[cnt++] = c;
            }
        }
        return cnt;
    }

    public String longestCommonPrefix(String[] strs) {
        Trie2 trie2 = new Trie2();
        for (String str : strs) {
            trie2.insert(str);
        }

        Trie2.Node node = trie2.getRoot();
        int len = 0;
        while (node.getChildren().size() == 1) {
            ++len;
            Character key = node.getChildren().keySet().iterator().next();
            node = node.getChildren().get(key);
        }
        return strs[0].substring(0, len);
    }

    class Trie2 {
        private Node root = new Node(null, 0);

        public Node getRoot() {
            return root;
        }

        //
        public class Node {
            //
            private Character aChar;
            private int value;
            //
            private Map<Character, Node> children = new HashMap<>();

            public Node(Character aChar, int value) {
                this.aChar = aChar;
                this.value = value;
            }

            public Map<Character, Node> getChildren() {
                return children;
            }
        }

        public void insert(String str) {
            if (str != null) {
                Node node = root;
                for (int i = 0; i < str.length(); i++) {
                    char ch = str.charAt(i);
                    node = insert(node, ch);
                }
            }
        }


        private Node insert(Node node, char ca) {
            Node cn = node.children.get(ca);
            if (cn == null) {
                cn = new Node(ca, 1);
                node.children.put(ca, cn);
            }
            return cn;
        }

    }


}
